var e = require;
var t = module;

!(function (e) {
    if ("object" == (typeof t === "undefined" ? "undefined" : typeof t) && "object" == typeof t.exports)
        t.exports = e();
    else if ("function" == typeof define && define.amd) define([], e);
    else {
        var o = e();
        (window.astar = o.astar), (window.Graph = o.Graph);
    }
})(function () {
    function e(e) {
        for (var t = e, o = []; t.parent; ) {
            o.unshift(t), (t = t.parent);
        }
        return o;
    }
    var t = {
        search: function search(o, n, a, r) {
            o.cleanDirty();
            var s = (r = r || {}).heuristic || t.heuristics.manhattan,
                d = r.closest || !1,
                c = new i(function (e) {
                    return e.f;
                }),
                l = n;
            for (n.h = s(n, a), o.markDirty(n), c.push(n); c.size() > 0; ) {
                var h = c.pop();
                if (h === a) return e(h);
                h.closed = !0;
                for (var u = o.neighbors(h), p = 0, f = u.length; p < f; ++p) {
                    var m = u[p];
                    if (!m.closed && !m.isWall()) {
                        var g = h.g + m.getCost(h),
                            w = m.visited;
                        (!w || g < m.g) &&
                            ((m.visited = !0),
                            (m.parent = h),
                            (m.h = m.h || s(m, a)),
                            (m.g = g),
                            (m.f = m.g + m.h),
                            o.markDirty(m),
                            d && (m.h < l.h || (m.h === l.h && m.g < l.g)) && (l = m),
                            w ? c.rescoreElement(m) : c.push(m));
                    }
                }
            }
            return d ? e(l) : [];
        },
        heuristics: {
            manhattan: function manhattan(e, t) {
                return Math.abs(t.x - e.x) + Math.abs(t.y - e.y);
            },
            diagonal: function diagonal(e, t) {
                var o = Math.sqrt(2),
                    n = Math.abs(t.x - e.x),
                    i = Math.abs(t.y - e.y);
                return 1 * (n + i) + (o - 2) * Math.min(n, i);
            }
        },
        cleanNode: function cleanNode(e) {
            (e.f = 0), (e.g = 0), (e.h = 0), (e.visited = !1), (e.closed = !1), (e.parent = null);
        }
    };
    function o(e, t) {
        (t = t || {}), (this.nodes = []), (this.diagonal = !!t.diagonal), (this.grid = []);
        for (var o = 0; o < e.length; o++) {
            this.grid[o] = [];
            for (var i = 0, a = e[o]; i < a.length; i++) {
                var r = new n(o, i, a[i]);
                (this.grid[o][i] = r), this.nodes.push(r);
            }
        }
        this.init();
    }
    function n(e, t, o) {
        (this.x = e), (this.y = t), (this.weight = o);
    }
    function i(e) {
        (this.content = []), (this.scoreFunction = e);
    }
    return (
        (o.prototype.init = function () {
            this.dirtyNodes = [];
            for (var e = 0; e < this.nodes.length; e++) {
                t.cleanNode(this.nodes[e]);
            }
        }),
        (o.prototype.cleanDirty = function () {
            for (var e = 0; e < this.dirtyNodes.length; e++) {
                t.cleanNode(this.dirtyNodes[e]);
            }
            this.dirtyNodes = [];
        }),
        (o.prototype.markDirty = function (e) {
            this.dirtyNodes.push(e);
        }),
        (o.prototype.neighbors = function (e) {
            var t = [],
                o = e.x,
                n = e.y,
                i = this.grid;
            return (
                i[o - 1] && i[o - 1][n] && t.push(i[o - 1][n]),
                i[o + 1] && i[o + 1][n] && t.push(i[o + 1][n]),
                i[o] && i[o][n - 1] && t.push(i[o][n - 1]),
                i[o] && i[o][n + 1] && t.push(i[o][n + 1]),
                this.diagonal &&
                    (i[o - 1] && i[o - 1][n - 1] && t.push(i[o - 1][n - 1]),
                    i[o + 1] && i[o + 1][n - 1] && t.push(i[o + 1][n - 1]),
                    i[o - 1] && i[o - 1][n + 1] && t.push(i[o - 1][n + 1]),
                    i[o + 1] && i[o + 1][n + 1] && t.push(i[o + 1][n + 1])),
                t
            );
        }),
        (o.prototype.toString = function () {
            for (var e = [], t = this.grid, o = 0; o < t.length; o++) {
                for (var n = [], i = t[o], a = 0; a < i.length; a++) {
                    n.push(i[a].weight);
                }
                e.push(n.join(" "));
            }
            return e.join("\n");
        }),
        (n.prototype.toString = function () {
            return "[" + this.x + " " + this.y + "]";
        }),
        (n.prototype.getCost = function (e) {
            return e && e.x != this.x && e.y != this.y ? 1.41421 * this.weight : this.weight;
        }),
        (n.prototype.isWall = function () {
            return 0 === this.weight;
        }),
        (i.prototype = {
            push: function push(e) {
                this.content.push(e), this.sinkDown(this.content.length - 1);
            },
            pop: function pop() {
                var e = this.content[0],
                    t = this.content.pop();
                return this.content.length > 0 && ((this.content[0] = t), this.bubbleUp(0)), e;
            },
            remove: function remove(e) {
                var t = this.content.indexOf(e),
                    o = this.content.pop();
                t !== this.content.length - 1 &&
                    ((this.content[t] = o),
                    this.scoreFunction(o) < this.scoreFunction(e) ? this.sinkDown(t) : this.bubbleUp(t));
            },
            size: function size() {
                return this.content.length;
            },
            rescoreElement: function rescoreElement(e) {
                this.sinkDown(this.content.indexOf(e));
            },
            sinkDown: function sinkDown(e) {
                for (var t = this.content[e]; e > 0; ) {
                    var o = ((e + 1) >> 1) - 1,
                        n = this.content[o];
                    if (!(this.scoreFunction(t) < this.scoreFunction(n))) break;
                    (this.content[o] = t), (this.content[e] = n), (e = o);
                }
            },
            bubbleUp: function bubbleUp(e) {
                for (var t = this.content.length, o = this.content[e], n = this.scoreFunction(o); ; ) {
                    var i,
                        a = (e + 1) << 1,
                        r = a - 1,
                        s = null;
                    if (r < t) {
                        var d = this.content[r];
                        (i = this.scoreFunction(d)) < n && (s = r);
                    }
                    if (a < t) {
                        var c = this.content[a];
                        this.scoreFunction(c) < (null === s ? n : i) && (s = a);
                    }
                    if (null === s) break;
                    (this.content[e] = this.content[s]), (this.content[s] = o), (e = s);
                }
            }
        }),
        {astar: t, Graph: o}
    );
});
